package junior.其他;

public class No3 {
    //                  颠倒二进制位
    // 颠倒给定的 32 位无符号整数的二进制位。
    //提示：
    //    请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类
    //    型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
    //    在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输
    //    出表示有符号整数 -1073741825。

    //----------------------------------------------------------------------------------------------
    //                          成功
    //想法：分为正数和负数进行右移操作，右移之前先将最后一位取出来
    /*
    public int reverseBits(int n) {
        int res = 0,temp = 31;

        while (temp >= 0) {
            int num = n & 1;

            n = n >> 1;

            //与运算后为1才进行加操作
            if (num == 1) {
                //double强转之后出问题了，精度缺失了（计算机组成原理中有讲到，浮点型的强转成整形的，精度会缺失），导致数值少了1
                res = res + (int)Math.pow(2,temp);
                if (temp == 31) {
                    res += 1;
                }
            }

            temp--;
        }

        return res;
    }
    */
    //----------------------------------------------------------------------------------------------

    //----------------------------------------------------------------------------------------------
    //                          另一种解法：
    //使用res存放结果，每次循环时：res先进行左移一位，腾出空间来存放n的当前最低位，然后让n和1作&运算得到当前的最低位，再
    // 让res加上此数，可以使用|运算进行加操作，因为n&1的结果只会是0或1，最后再让n右移一位。循环执行32次
    /*
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            //res先往左移一位，把最后一个位置空出来，
            //用来存放n的最后一位数字
            res <<= 1;
            //res加上n的最后一位数字
            res |= n & 1;
            //n往右移一位，把最后一位数字去掉
            n >>= 1;
        }
        return res;
    }
    */
    //-----------------------------------------------------------------------------------------------


    //-----------------------------------------------------------------------------------------------
    //                      解法三：
    //把高位与低位互相调换就可以了，不过得要分别操作
    //      注意：<<运算符左边是要左移的数，而右边是左移的位数，>>运算符同理
    /*
    public int reverseBits(int n) {
        int res = 0;
        //把低16位移到高16上
        for (int i = 0; i < 16; i++) {
            //  每次左移的位数需要注意：（31-i*2）是左移位数，因为最低位：1 要移到最高位：32 上去
            //左移的位数是32-1 = 31；而第2位的数要移到第31位上去，左移的位数是31-2 = 29；最低位
            //每加一位，所需要移动的位数就要减2因为与要移到的位之间的距离每次缩短了2
            res |= (n & (1 << i)) << (31 - i * 2);
        }
        //把高16位移到低16位上
        for (int i = 16; i < 32; i++) {
            res |= (n & (1 << i)) >>> (i * 2 - 31);
        }
        return res;
    }*/
    //-------------------------------------------------------------------------------------------


    //-------------------------------------------------------------------------------------------
    //                      解法四：分治法
    //将前16位与后16位整体调换，然后在前16位/后16位中再分别调换前8位与后8位，如此直至2位调换
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);
        //这里需要注意：n&0xff00ff00的意思是取出前16位中的前8位和后16位中的前8位，将这个数右移8位，也就是将前16位中的
        // 前8位和后16位中的前8位移到了后8位去，后面的操作同理
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
    //-------------------------------------------------------------------------------------------
}
